def partition(arr,low,high): 
    i = low-1         # 最小元素索引,正确
    pivot = arr[high]       
    for j in range(low , high):   
        # 当前元素小于或等于 pivot 
        if  arr[j] <= pivot:          
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i]   
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
 
# 快速排序函数
def quickSort(arr,low,high): 
    if low < high:  
        pi = partition(arr,low,high)   
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
arr = [12, 2, 8, 9, 4, 5] 
n = len(arr) 
quickSort(arr,0,n-1)
